﻿'//************************************************************************************
'// BigInteger Class Version 1.03
'//
'// Copyright (c) 2002 Chew Keong TAN
'// All rights reserved.
'//
'// Permission is hereby granted, free of charge, to any person obtaining a
'// copy of this software and associated documentation files (the
'// "Software"), to deal in the Software without restriction, including
'// without limitation the rights to use, copy, modify, merge, publish,
'// distribute, and/or sell copies of the Software, and to permit persons
'// to whom the Software is furnished to do so, provided that the above
'// copyright notice(s) and this permission notice appear in all copies of
'// the Software and that both the above copyright notice(s) and this
'// permission notice appear in supporting documentation.
'//
'// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
'// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
'// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
'// OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
'// HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
'// INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
'// FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
'// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
'// WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
'//
'//
'// Disclaimer
'// ----------
'// Although reasonable care has been taken to ensure the correctness of this
'// implementation, this code should never be used in any application without
'// proper verification and testing.  I disclaim all liability and responsibility
'// to any person or entity with respect to any loss or damage caused, or alleged
'// to be caused, directly or indirectly, by the use of this BigInteger class.
'//
'// Comments, bugs and suggestions to
'// (http://www.codeproject.com/csharp/biginteger.asp)
'//
'//
'// Overloaded Operators +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, --, ~
'//
'// Features
'// --------
'// 1) Arithmetic operations involving large signed integers (2's complement).
'// 2) Primality test using Fermat little theorm, Rabin Miller's method,
'//    Solovay Strassen's method and Lucas strong pseudoprime.
'// 3) Modulo exponential with Barrett's reduction.
'// 4) Inverse modulo.
'// 5) Pseudo prime generation.
'// 6) Co-prime generation.
'//
'//
'// Known Problem
'// -------------
'// This pseudoprime passes my implementation of
'// primality test but failed in JDK's isProbablePrime test.
'//
'//       byte[] pseudoPrime1 = { (byte)0x00,
'//             (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD, (byte)0x70, (byte)0x6A,
'//             (byte)0x9F, (byte)0xF0, (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
'//             (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9, (byte)0x55, (byte)0xB3,
'//             (byte)0x85, (byte)0x32, (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
'//             (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E, (byte)0xEA, (byte)0x56,
'//             (byte)0x8D, (byte)0x8C, (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
'//             (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C, (byte)0x12, (byte)0x41,
'//             (byte)0x1E, (byte)0xF1, (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
'//             (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8, (byte)0xE8, (byte)0xAF,
'//             (byte)0x42, (byte)0xF4, (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
'//             (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
'//       }
'//
'//
'// Change Log
'// ----------
'// 1) September 23, 2002 (Version 1.03)
'//    - Fixed operator- to give correct data length.
'//    - Added Lucas sequence generation.
'//    - Added Strong Lucas Primality test.
'//    - Added integer square root method.
'//    - Added setBit/unsetBit methods.
'//    - New isProbablePrime() method which do not require the
'//      confident parameter.
'//
'// 2) August 29, 2002 (Version 1.02)
'//    - Fixed bug in the exponentiation of negative numbers.
'//    - Faster modular exponentiation using Barrett reduction.
'//    - Added getBytes() method.
'//    - Fixed bug in ToHexString method.
'//    - Added overloading of ^ operator.
'//    - Faster computation of Jacobi symbol.
'//
'// 3) August 19, 2002 (Version 1.01)
'//    - Big integer is stored and manipulated as unsigned integers (4 bytes) instead of
'//      individual bytes this gives significant performance improvement.
'//    - Updated Fermat's Little Theorem test to use a^(p-1) mod p = 1
'//    - Added isProbablePrime method.
'//    - Updated documentation.
'//
'// 4) August 9, 2002 (Version 1.0)
'//    - Initial Release.
'//
'//
'// References
'// [1] D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2,
'//     3rd Edition, Addison-Wesley, 1998.
'//
'// [2] K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed,
'//     Addison-Wesley, 1993.
'//
'// [3] B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996.
'//
'// [4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography",
'//     CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac
'//
'// [5] A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular
'//     Reduction Functions," Proc. CRYPTO'93, pp.175-186.
'//
'// [6] R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation,
'//     Vol. 35, No. 152, Oct 1980, pp. 1391-1417.
'//
'// [7] H. C. Williams, "+douard Lucas and Primality Testing", Canadian Mathematical
'//     Society Series of Monographs and Advance Texts, vol. 22, John Wiley & Sons, New York,
'//     NY, 1998.
'//
'// [8] P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag,
'//     New York, NY, 1995.
'//
'// [9] M. Joye and J.-J. Quisquater, "Efficient computation of full Lucas sequences",
'//     Electronics Letters, 32(6), 1996, pp 537-538.
'//
'//************************************************************************************

Imports System
'// Modified by Foole for WoW SRP6 usage.
'// It reverses the byte array when importing or exporting
'// Added an implicit byte[] cast operator
'// Removed a lot of code I don't need

Public Class BigInteger

    '// maximum length of the BigInteger in uint (4 bytes)
    '// change this to suit the required level of precision.

    Private Const maxLength As Integer = 70

    '// primes smaller than 2000 to test the generated prime number

    Public Static ReadOnly primesBelow2000 As Integer() = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, _
                                                           101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, _
                                                           211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, _
                                                           307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, _
                                                           401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, _
                                                           503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, _
                                                           601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, _
                                                           701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, _
                                                           809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, _
                                                           907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, _
                                                           1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, _
                                                           1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, _
                                                           1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, _
                                                           1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, _
                                                           1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, _
                                                           1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, _
                                                           1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, _
                                                           1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, _
                                                           1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, _
                                                           1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999}


    Private data As UInteger() = Nothing            '// stores bytes from the Big Integer
    Public dataLength As Integer                    '// number of actual chars used

#region 'Constructors'

    '//***********************************************************************
    '// Constructor (Default value for BigInteger is 0
    '//***********************************************************************

    Public Sub New()
        data = New UInteger(maxLength)
        dataLength = 1
    End Sub


    '//***********************************************************************
    '// Constructor (Default value provided by long)
    '//***********************************************************************

    Public Sub New(ByVal value As Long)
        data = New UInteger(maxLength)
        tempVal as long = value

        '// copy bytes from long to BigInteger without any assumption of
        '// the length of the long datatype

        dataLength = 0
        while(value != 0 && dataLength < maxLength)
            data(dataLength) = (uinteger)(value & &HFFFFFFFF)
            value >>= 32
            dataLength++
        End While

        If (tempVal > 0) Then         '// overflow check for +ve value
            if(value != 0 || (data[maxLength-1] & 0x80000000) != 0) then Throw (New ArithmeticException("Positive overflow in constructor."))
        ElseIf (tempVal < 0) Then    '// underflow check for -ve value
            if(value != -1 || (data[dataLength-1] & 0x80000000) == 0) then Throw (New ArithmeticException("Negative underflow in constructor."))
        End If
        If (dataLength = 0) Then dataLength = 1

    End Sub

    '//***********************************************************************
    '// Constructor (Default value provided by ulong)
    '//***********************************************************************

    Public Sub New(ByVal value As ULong)
        data = New UInteger(maxLength)
        '// copy bytes from ulong to BigInteger without any assumption of
        '// the length of the ulong datatype
        dataLength = 0
        while(value != 0 && dataLength < maxLength)
            data(dataLength) = (uinteger)(value & &HFFFFFFFF)
            value >>= 32
            dataLength++
        End While

        if(value != 0 || (data[maxLength-1] & 0x80000000) != 0) then Throw (New ArithmeticException("Positive overflow in constructor."))
        if(dataLength == 0) then dataLength = 1

    End Sub

    '//***********************************************************************
    '// Constructor (Default value provided by BigInteger)
    '//***********************************************************************

    Public Sub New(ByVal bi As BigInteger)
        data = New UInteger(maxLength)
        dataLength = bi.dataLength
        for(i = 0 to dataLength)
            data(i) = bi.data(i)
        Next
    End Sub


    '//***********************************************************************
    '// Constructor (Default value provided by a string of digits of the
    '//              specified base)
    '//
    '// Example (base 10)
    '// -----------------
    '// To initialize "a" with the default value of 1234 in base 10
    '//      BigInteger a = new BigInteger("1234", 10)
    '//
    '// To initialize "a" with the default value of -1234
    '//      BigInteger a = new BigInteger("-1234", 10)
    '//
    '// Example (base 16)
    '// -----------------
    '// To initialize "a" with the default value of 0x1D4F in base 16
    '//      BigInteger a = new BigInteger("1D4F", 16)
    '//
    '// To initialize "a" with the default value of -0x1D4F
    '//      BigInteger a = new BigInteger("-1D4F", 16)
    '//
    '// Note that string values are specified in the <sign><magnitude>
    '// format.
    '//
    '//***********************************************************************

    Public Sub New(ByVal value As String, ByVal radix As Integer)
        BigInteger(multiplier = New BigInteger(1))
        BigInteger(result = New BigInteger())
        value = (value.ToUpper()).Trim()
        Integer limit = 0
        If (value(0) = "-") Then
            limit = 1
            For i = (value.Length - 1) To limit
                int posVal = (integer)value(i)
            Next
            if (posVal >= "0" && posVal <= "9") then
                posVal -= "0"
                ElseIf (posVal >= "A" && posVal <= "Z")
                posVal = (posVal - "A") + 10
            Else
                posVal = 9999999       '// arbitrary large
                If (posVal >= radix) Then
                    Throw (New ArithmeticException("Invalid string in constructor."))
                Else
                    If (value(0) = "-") Then
                        posVal = -posVal
                        result += (multiplier * posVal)
                        If ((i - 1) >= limit) Then (multiplier *= radix)
                    End If
                End If

                If (value(0) = "-") Then     '// negative values
                    If ((result.data(maxLength - 1) & &H80000000) = 0) Then Throw (New ArithmeticException("Negative underflow in constructor."))
                Else    '// positive values
                    if((result.data(maxLength-1) & &H80000000) != 0) then Throw (New ArithmeticException("Positive overflow in constructor."))
                End If

                data = New UInteger(maxLength)
                For i = 0 To result.dataLength
                    data(i) = result.data(i)
                Next
                dataLength = result.dataLength
            End If
    End Sub

    '//***********************************************************************
    '// Constructor (Default value provided by an array of bytes)
    '//
    '// The lowest index of the input byte array (i.e [0]) should contain the
    '// most significant byte of the number, and the highest index should
    '// contain the least significant byte.
    '//
    '// E.g.
    '// To initialize "a" with the default value of 0x1D4F in base 16
    '//      byte[] temp = { 0x1D, 0x4F }
    '//      BigInteger a = new BigInteger(temp)
    '//
    '// Note that this method of initialization does not allow the
    '// sign to be specified.
    '//
    '//***********************************************************************

        public static byte[] CloneAndReverse(byte[] Data)
        {
        	byte[] temp = (byte[])Data.Clone()
                                                Array.Reverse(temp)
                                                Return temp
        }

        public BigInteger(byte[] inData)
        {
        	// Customised by Foole - Reverse the array
                                                inData = CloneAndReverse(inData)
                                                dataLength = inData.Length >> 2

            int leftOver = inData.Length & 0x3
            if(leftOver != 0)         // length not multiples of 4
                dataLength++


                                                    If (dataLength > maxLength) Then
                                                        Throw (New ArithmeticException("Byte overflow in constructor."))

            data = new uint[maxLength]

            for(int i = inData.Length - 1, j = 0 i >= 3 i -= 4, j++)
            {
                    data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
                                     (inData[i-1] <<  8) + inData[i])
            }

            if(leftOver == 1)
                    data[dataLength-1] = (uint)inData[0]
            else if(leftOver == 2)
                    data[dataLength-1] = (uint)((inData[0] << 8) + inData[1])
            else if(leftOver == 3)
                    data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2])

            while(dataLength > 1 && data[dataLength-1] == 0)
                    dataLength--
                //Console.WriteLine("Len = " + dataLength)
        }


    '//***********************************************************************
    '// Constructor (Default value provided by an array of bytes of the
    '// specified length.)
    '//***********************************************************************

        public BigInteger(byte[] inData, int inLen)
        {
                                                                    dataLength = inLen >> 2

                int leftOver = inLen & 0x3
                if(leftOver != 0)         // length not multiples of 4
                        dataLength++

                if(dataLength > maxLength || inLen > inData.Length)
                                                                            Throw (New ArithmeticException("Byte overflow in constructor."))


                data = new uint[maxLength]

                for(int i = inLen - 1, j = 0 i >= 3 i -= 4, j++)
                {
                        data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
                                         (inData[i-1] <<  8) + inData[i])
                }

                if(leftOver == 1)
                        data[dataLength-1] = (uint)inData[0]
                else if(leftOver == 2)
                        data[dataLength-1] = (uint)((inData[0] << 8) + inData[1])
                else if(leftOver == 3)
                        data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2])


                if(dataLength == 0)
                                                                                        dataLength = 1

                while(dataLength > 1 && data[dataLength-1] == 0)
                        dataLength--

                //Console.WriteLine("Len = " + dataLength)
        }


    '//***********************************************************************
    '// Constructor (Default value provided by an array of unsigned integers)
    '//*********************************************************************

        public BigInteger(uint[] inData)
        {
                                                                                            dataLength = inData.Length

                                                                                            If (dataLength > maxLength) Then
                                                                                                Throw (New ArithmeticException("Byte overflow in constructor."))

                data = new uint[maxLength]

                for(int i = dataLength - 1, j = 0 i >= 0 i--, j++)
                        data[j] = inData[i]

                while(dataLength > 1 && data[dataLength-1] == 0)
                        dataLength--

                //Console.WriteLine("Len = " + dataLength)
        }


    '//***********************************************************************
    '// Overloading of the typecast operator.
    '// For BigInteger bi = 10
    '//***********************************************************************
#End Region 'Constructors'

#region 'Operators'
        public static implicit operator BigInteger(long value)
        {
                                                                                                        Return (New BigInteger(value))
        }

        public static implicit operator BigInteger(ulong value)
        {
                                                                                                        Return (New BigInteger(value))
        }

        public static implicit operator BigInteger(int value)
        {
                return (new BigInteger((long)value))
        }

        public static implicit operator BigInteger(uint value)
        {
                return (new BigInteger((ulong)value))
        }


    '//***********************************************************************
    '// Overloading of addition operator
    '//***********************************************************************

        public static BigInteger operator +(BigInteger bi1, BigInteger bi2)
        {
                                                                                                        BigInteger(result = New BigInteger())

                result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength

                long carry = 0
                for(int i = 0 i < result.dataLength i++)
                {
                        long sum = (long)bi1.data[i] + (long)bi2.data[i] + carry
                                                                                                            carry = sum >> 32
                        result.data[i] = (uint)(sum & 0xFFFFFFFF)
                }

                if(carry != 0 && result.dataLength < maxLength)
                {
                        result.data[result.dataLength] = (uint)(carry)
                        result.dataLength++
                }

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--


                // overflow check
                                                                                                                    Int(lastPos = maxLength - 1)
                if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
                   (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
                {
                                                                                                                        Throw (New ArithmeticException())
                }

                                                                                                                        Return result
        }


    '//***********************************************************************
    '// Overloading of the unary ++ operator
    '//***********************************************************************

        public static BigInteger operator ++(BigInteger bi1)
        {
                                                                                                                        BigInteger(result = New BigInteger(bi1))

                long val, carry = 1
                                                                                                                        Int(index = 0)

                while(carry != 0 && index < maxLength)
                {
                        val = (long)(result.data[index])
                        val++

                        result.data[index] = (uint)(val & 0xFFFFFFFF)
                                                                                                                            carry = Val() >> 32

                        index++
                }

                                                                                                                            If (index > result.dataLength) Then
                                                                                                                                result.dataLength = index
                                                                                                                            Else
                {
                        while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                                result.dataLength--
                }

                // overflow check
                                                                                                                                    Int(lastPos = maxLength - 1)

                // overflow if initial value was +ve but ++ caused a sign
                // change to negative.

                if((bi1.data[lastPos] & 0x80000000) == 0 &&
                   (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
                {
                                                                                                                                        Throw (New ArithmeticException("Overflow in ++."))
                }
                                                                                                                                        Return result
        }


    '//***********************************************************************
    '// Overloading of subtraction operator
    '//***********************************************************************

        public static BigInteger operator -(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                        BigInteger(result = New BigInteger())

                result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength

                long carryIn = 0
                for(int i = 0 i < result.dataLength i++)
                {
                        long diff

                        diff = (long)bi1.data[i] - (long)bi2.data[i] - carryIn
                        result.data[i] = (uint)(diff & 0xFFFFFFFF)

                                                                                                                                            If (diff < 0) Then
                                                                                                                                                carryIn = 1
                                                                                                                                            Else
                                                                                                                                                carryIn = 0
                }

                // roll over to negative
                if(carryIn != 0)
                {
                        for(int i = result.dataLength i < maxLength i++)
                                result.data[i] = 0xFFFFFFFF
                                                                                                                                                        result.dataLength = maxLength
                }

                // fixed in v1.03 to give correct datalength for a - (-b)
                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                // overflow check

                                                                                                                                                            Int(lastPos = maxLength - 1)
                if((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
                   (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
                {
                                                                                                                                                                Throw (New ArithmeticException())
                }

                                                                                                                                                                Return result
        }


    '//***********************************************************************
    '// Overloading of the unary -- operator
    '//***********************************************************************

        public static BigInteger operator --(BigInteger bi1)
        {
                                                                                                                                                                BigInteger(result = New BigInteger(bi1))

                long val
                                                                                                                                                                bool(carryIn = True)
                                                                                                                                                                Int(index = 0)

                while(carryIn && index < maxLength)
                {
                        val = (long)(result.data[index])
                        val--

                        result.data[index] = (uint)(val & 0xFFFFFFFF)

                                                                                                                                                                    If (Val() >= 0) Then
                                                                                                                                                                        carryIn = False

                        index++
                }

                                                                                                                                                                        If (index > result.dataLength) Then
                                                                                                                                                                            result.dataLength = index

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                // overflow check
                                                                                                                                                                                Int(lastPos = maxLength - 1)

                // overflow if initial value was -ve but -- caused a sign
                // change to positive.

                if((bi1.data[lastPos] & 0x80000000) != 0 &&
                   (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
                {
                                                                                                                                                                                    Throw (New ArithmeticException("Underflow in --."))
                }

                                                                                                                                                                                    Return result
        }


    '//***********************************************************************
    '// Overloading of multiplication operator
    '//***********************************************************************

        public static BigInteger operator *(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                    Int(lastPos = maxLength - 1)
                                                                                                                                                                                    bool(bi1Neg = False, bi2Neg = False)

                // take the absolute value of the inputs
                                                                                                                                                                                    Try
                {
                        if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
                        {
                                bi1Neg = true bi1 = -bi1
                        }
                        if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
                        {
                                bi2Neg = true bi2 = -bi2
                        }
                }
                catch(Exception) {}

                                                                                                                                                                                        BigInteger(result = New BigInteger())

                // multiply the absolute values
                                                                                                                                                                                        Try
                {
                        for(int i = 0 i < bi1.dataLength i++)
                        {
                                if(bi1.data[i] == 0)    continue

                                ulong mcarry = 0
                                for(int j = 0, k = i j < bi2.dataLength j++, k++)
                                {
                                        // k = i + j
                                        ulong val = ((ulong)bi1.data[i] * (ulong)bi2.data[j]) +
                                                     (ulong)result.data[k] + mcarry

                                        result.data[k] = (uint)(val & 0xFFFFFFFF)
                                                                                                                                                                                                        mcarry = (Val() >> 32)
                                }

                                if(mcarry != 0)
                                        result.data[i+bi2.dataLength] = (uint)mcarry
                        }
                }
                catch(Exception)
                {
                                                                                                                                                                                            Throw (New ArithmeticException("Multiplication overflow."))
                }


                                                                                                                                                                                            result.dataLength = bi1.dataLength + bi2.dataLength
                                                                                                                                                                                            If (result.dataLength > maxLength) Then
                                                                                                                                                                                                result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                // overflow check (result is -ve)
                if((result.data[lastPos] & 0x80000000) != 0)
                {
                        if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000)    // different sign
                        {
                                // handle the special case where multiplication produces
                                // a max negative number in 2's complement.

                                if(result.dataLength == 1)
                                                                                                                                                                                                                Return result
                                                                                                                                                                                                            Else
                                {
                                                                                                                                                                                                                bool(isMaxNeg = True)
                                        for(int i = 0 i < result.dataLength - 1 && isMaxNeg i++)
                                        {
                                                if(result.data[i] != 0)
                                                                                                                                                                                                                        isMaxNeg = False
                                        }

                                                                                                                                                                                                                        If (isMaxNeg) Then
                                                                                                                                                                                                                            Return result
                                }
                        }

                                                                                                                                                                                                                            Throw (New ArithmeticException("Multiplication overflow."))
                }

                // if input has different signs, then result is -ve
                if(bi1Neg != bi2Neg)
                                                                                                                                                                                                                                Return -result

                                                                                                                                                                                                                                Return result
        }



    '//***********************************************************************
    '// Overloading of unary << operators
    '//***********************************************************************

        public static BigInteger operator <<(BigInteger bi1, int shiftVal)
        {
                                                                                                                                                                                                                                BigInteger(result = New BigInteger(bi1))
                                                                                                                                                                                                                                result.dataLength = shiftLeft(result.data, shiftVal)

                                                                                                                                                                                                                                Return result
        }

    '//***********************************************************************
    '// Overloading of unary >> operators
    '//***********************************************************************

        public static BigInteger operator >>(BigInteger bi1, int shiftVal)
        {
                                                                                                                                                                                                                                BigInteger(result = New BigInteger(bi1))
                                                                                                                                                                                                                                result.dataLength = shiftRight(result.data, shiftVal)


                if((bi1.data[maxLength-1] & 0x80000000) != 0) // negative
                {
                        for(int i = maxLength - 1 i >= result.dataLength i--)
                                result.data[i] = 0xFFFFFFFF

                        uint mask = 0x80000000
                        for(int i = 0 i < 32 i++)
                        {
                                if((result.data[result.dataLength-1] & mask) != 0)
                                                                                                                                                                                                                                                break()

                                result.data[result.dataLength-1] |= mask
                                                                                                                                                                                                                                                mask >>= 1
                        }
                                                                                                                                                                                                                                                result.dataLength = maxLength
                }

                                                                                                                                                                                                                                                Return result
        }

        public static implicit operator byte[](BigInteger Value)
        {
                                                                                                                                                                                                                                                Return Value.getBytes()
        }

#endregion Operators

        // least significant bits at lower part of buffer

        private static int shiftLeft(uint[] buffer, int shiftVal)
        {
                                                                                                                                                                                                                                                Int(shiftAmount = 32)
                                                                                                                                                                                                                                                Int(bufLen = Buffer.Length)

                while(bufLen > 1 && buffer[bufLen-1] == 0)
                        bufLen--

                for(int count = shiftVal count > 0)
                {
                                                                                                                                                                                                                                                        If (count < shiftAmount) Then
                                                                                                                                                                                                                                                            shiftAmount = count

                        //Console.WriteLine("shiftAmount = {0}", shiftAmount)

                        ulong carry = 0
                        for(int i = 0 i < bufLen i++)
                        {
                                ulong val = ((ulong)buffer[i]) << shiftAmount
                                val |= carry

                                buffer[i] = (uint)(val & 0xFFFFFFFF)
                                                                                                                                                                                                                                                                carry = Val() >> 32
                        }

                        if(carry != 0)
                        {
                                                                                                                                                                                                                                                                    If (bufLen + 1 <= Buffer.Length) Then
                                {
                                        buffer[bufLen] = (uint)carry
                                        bufLen++
                                }
                        }
                                                                                                                                                                                                                                                                        count -= shiftAmount
                }
                                                                                                                                                                                                                                                                        Return bufLen
        }

        private static int shiftRight(uint[] buffer, int shiftVal)
        {
                                                                                                                                                                                                                                                                        Int(shiftAmount = 32)
                                                                                                                                                                                                                                                                        Int(invShift = 0)
                                                                                                                                                                                                                                                                        Int(bufLen = Buffer.Length)

                while(bufLen > 1 && buffer[bufLen-1] == 0)
                        bufLen--

                //Console.WriteLine("bufLen = " + bufLen + " buffer.Length = " + buffer.Length)

                for(int count = shiftVal count > 0)
                {
                                                                                                                                                                                                                                                                                If (count < shiftAmount) Then
                        {
                                                                                                                                                                                                                                                                                    shiftAmount = count
                                                                                                                                                                                                                                                                                    invShift = 32 - shiftAmount
                        }

                        //Console.WriteLine("shiftAmount = {0}", shiftAmount)

                        ulong carry = 0
                        for(int i = bufLen - 1 i >= 0 i--)
                        {
                                ulong val = ((ulong)buffer[i]) >> shiftAmount
                                val |= carry

                                carry = ((ulong)buffer[i]) << invShift
                                                                                                                                                                                                                                                                                        Buffer([i] = (uint)(Val))
                        }

                                                                                                                                                                                                                                                                                        count -= shiftAmount
                }

                while(bufLen > 1 && buffer[bufLen-1] == 0)
                        bufLen--

                                                                                                                                                                                                                                                                                            Return bufLen
        }


    '//***********************************************************************
    '// Overloading of the NOT operator (1's complement)
    '//***********************************************************************

        public static BigInteger operator ~(BigInteger bi1)
        {
                                                                                                                                                                                                                                                                                            BigInteger(result = New BigInteger(bi1))

                for(int i = 0 i < maxLength i++)
                        result.data[i] = (uint)(~(bi1.data[i]))

                                                                                                                                                                                                                                                                                                result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                                                                                                                                                                                                                                                                                                    Return result
        }


    '//***********************************************************************
    '// Overloading of the NEGATE operator (2's complement)
    '//***********************************************************************

        public static BigInteger operator -(BigInteger bi1)
        {
                // handle neg of zero separately since it'll cause an overflow
                // if we proceed.

                if(bi1.dataLength == 1 && bi1.data[0] == 0)
                                                                                                                                                                                                                                                                                                        Return (New BigInteger())

                                                                                                                                                                                                                                                                                                        BigInteger(result = New BigInteger(bi1))

                // 1's complement
                for(int i = 0 i < maxLength i++)
                        result.data[i] = (uint)(~(bi1.data[i]))

                // add one to result of 1's complement
                long val, carry = 1
                                                                                                                                                                                                                                                                                                            Int(index = 0)

                while(carry != 0 && index < maxLength)
                {
                        val = (long)(result.data[index])
                        val++

                        result.data[index] = (uint)(val & 0xFFFFFFFF)
                                                                                                                                                                                                                                                                                                                carry = Val() >> 32

                        index++
                }

                if((bi1.data[maxLength-1] & 0x80000000) == (result.data[maxLength-1] & 0x80000000))
                                                                                                                                                                                                                                                                                                                    Throw (New ArithmeticException("Overflow in negation.\n"))

                                                                                                                                                                                                                                                                                                                    result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--
                                                                                                                                                                                                                                                                                                                        Return result
        }


    '//***********************************************************************
    '// Overloading of equality operator
    '//***********************************************************************

        public static bool operator ==(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                        Return bi1.Equals(bi2)
        }


        public static bool operator !=(BigInteger bi1, BigInteger bi2)
        {
                return !(bi1.Equals(bi2))
        }

        public override bool Equals(object o)
        {
                BigInteger bi = (BigInteger)o

                if(this.dataLength != bi.dataLength)
                                                                                                                                                                                                                                                                                                                            Return False

                for(int i = 0 i < this.dataLength i++)
                {
                        if(this.data[i] != bi.data[i])
                                                                                                                                                                                                                                                                                                                                    Return False
                }
                                                                                                                                                                                                                                                                                                                                    Return True
        }


        public override int GetHashCode()
        {
                                                                                                                                                                                                                                                                                                                                    Return this.ToString().GetHashCode()
        }


    '//***********************************************************************
    '// Overloading of inequality operator
    '//***********************************************************************

        public static bool operator >(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                    Int(pos = maxLength - 1)

        	// bi1 is negative, bi2 is positive
        	if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
                                                                                                                                                                                                                                                                                                                                        Return False

                // bi1 is positive, bi2 is negative
        	else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
                                                                                                                                                                                                                                                                                                                                        Return True

                // same sign
        	int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength
	        for(pos = len - 1 pos >= 0 && bi1.data[pos] == bi2.data[pos] pos--)

                                                                                                                                                                                                                                                                                                                                            If (pos >= 0) Then
	        {
		        if(bi1.data[pos] > bi2.data[pos])
                                                                                                                                                                                                                                                                                                                                                    Return True
                                                                                                                                                                                                                                                                                                                                                    Return False
	        }
                                                                                                                                                                                                                                                                                                                                                    Return False
        }


        public static bool operator <(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                    Int(pos = maxLength - 1)

        	// bi1 is negative, bi2 is positive
        	if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
                                                                                                                                                                                                                                                                                                                                                        Return True

                // bi1 is positive, bi2 is negative
        	else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
                                                                                                                                                                                                                                                                                                                                                        Return False

        	// same sign
        	int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength
	        for(pos = len - 1 pos >= 0 && bi1.data[pos] == bi2.data[pos] pos--)

                                                                                                                                                                                                                                                                                                                                                            If (pos >= 0) Then
	        {
		        if(bi1.data[pos] < bi2.data[pos])
                                                                                                                                                                                                                                                                                                                                                                    Return True
                                                                                                                                                                                                                                                                                                                                                                    Return False
	        }
                                                                                                                                                                                                                                                                                                                                                                    Return False
        }


        public static bool operator >=(BigInteger bi1, BigInteger bi2)
        {
                return (bi1 == bi2 || bi1 > bi2)
        }


        public static bool operator <=(BigInteger bi1, BigInteger bi2)
        {
                return (bi1 == bi2 || bi1 < bi2)
        }


    '//***********************************************************************
    '// Private function that supports the division of two numbers with
    '// a divisor that has more than 1 digit.
    '//
    '// Algorithm taken from [1]
    '//***********************************************************************

        private static void multiByteDivide(BigInteger bi1, BigInteger bi2,
                                            BigInteger outQuotient, BigInteger outRemainder)
        {
                uint[] result = new uint[maxLength]

                                                                                                                                                                                                                                                                                                                                                                    Int(remainderLen = bi1.dataLength + 1)
                uint[] remainder = new uint[remainderLen]

                uint mask = 0x80000000
                uint val = bi2.data[bi2.dataLength - 1]
                                                                                                                                                                                                                                                                                                                                                                    Int(shift = 0, resultPos = 0)

                while(mask != 0 && (val & mask) == 0)
                {
                        shift++ mask >>= 1
                }

                //Console.WriteLine("shift = {0}", shift)
                //Console.WriteLine("Before bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength)

                for(int i = 0 i < bi1.dataLength i++)
                        remainder[i] = bi1.data[i]
                                                                                                                                                                                                                                                                                                                                                                            shiftLeft(remainder, shift)
                                                                                                                                                                                                                                                                                                                                                                            bi2 = bi2 << shift

                /*
                                                                                                                                                                                                                                                                                                                                                                            Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength)
                                                                                                                                                                                                                                                                                                                                                                            Console.WriteLine("dividend = " + bi1 + "\ndivisor = " + bi2)
                for(int q = remainderLen - 1 q >= 0 q--)
                        Console.Write("{0:x2}", remainder[q])
                                                                                                                                                                                                                                                                                                                                                                                Console.WriteLine()
                */

                                                                                                                                                                                                                                                                                                                                                                                Int(j = remainderLen - bi2.dataLength)
                                                                                                                                                                                                                                                                                                                                                                                Int(pos = remainderLen - 1)

                ulong firstDivisorByte = bi2.data[bi2.dataLength-1]
                ulong secondDivisorByte = bi2.data[bi2.dataLength-2]

                                                                                                                                                                                                                                                                                                                                                                                Int(divisorLen = bi2.dataLength + 1)
                uint[] dividendPart = new uint[divisorLen]

                                                                                                                                                                                                                                                                                                                                                                                While (j > 0)
                {
                        ulong dividend = ((ulong)remainder[pos] << 32) + (ulong)remainder[pos-1]
                        //Console.WriteLine("dividend = {0}", dividend)

                        ulong q_hat = dividend / firstDivisorByte
                        ulong r_hat = dividend % firstDivisorByte

                        //Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat)

                                                                                                                                                                                                                                                                                                                                                                                    bool(done = False)
                                                                                                                                                                                                                                                                                                                                                                                    While (!done)
                        {
                                                                                                                                                                                                                                                                                                                                                                                        done = True

                                if(q_hat == 0x100000000 ||
                                   (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-2]))
                                {
                                        q_hat--
                                                                                                                                                                                                                                                                                                                                                                                            r_hat += firstDivisorByte

                                        if(r_hat < 0x100000000)
                                                                                                                                                                                                                                                                                                                                                                                                done = False
                                }
                        }

                        for(int h = 0 h < divisorLen h++)
                                dividendPart[h] = remainder[pos-h]

                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(kk = New BigInteger(dividendPart))
                        BigInteger ss = bi2 * (long)q_hat

                        //Console.WriteLine("ss before = " + ss)
                                                                                                                                                                                                                                                                                                                                                                                                    While (ss > kk)
                        {
                                q_hat--
                                                                                                                                                                                                                                                                                                                                                                                                        ss -= bi2
                                //Console.WriteLine(ss)
                        }
                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(yy = kk - ss)

                        //Console.WriteLine("ss = " + ss)
                        //Console.WriteLine("kk = " + kk)
                        //Console.WriteLine("yy = " + yy)

                        for(int h = 0 h < divisorLen h++)
                                remainder[pos-h] = yy.data[bi2.dataLength-h]

                        /*
                                                                                                                                                                                                                                                                                                                                                                                                            Console.WriteLine("dividend = ")
                        for(int q = remainderLen - 1 q >= 0 q--)
                                Console.Write("{0:x2}", remainder[q])
                                                                                                                                                                                                                                                                                                                                                                                                                Console.WriteLine("\n************ q_hat = {0:X}\n", q_hat)
                        */

                        result[resultPos++] = (uint)q_hat

                        pos--
                        j--
                }

                                                                                                                                                                                                                                                                                                                                                                                                                outQuotient.dataLength = resultPos
                                                                                                                                                                                                                                                                                                                                                                                                                Int(y = 0)
                for(int x = outQuotient.dataLength - 1 x >= 0 x--, y++)
                        outQuotient.data[y] = result[x]
                for( y < maxLength y++)
                                                                                                                                                                                                                                                                                                                                                                                                                        outQuotient.data([y] = 0)

                while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
                        outQuotient.dataLength--

                if(outQuotient.dataLength == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                outQuotient.dataLength = 1

                                                                                                                                                                                                                                                                                                                                                                                                                                outRemainder.dataLength = shiftRight(remainder, shift)

                for(y = 0 y < outRemainder.dataLength y++)
                        outRemainder.data[y] = remainder[y]
                for( y < maxLength y++)
                                                                                                                                                                                                                                                                                                                                                                                                                                        outRemainder.data([y] = 0)
        }


    '//***********************************************************************
    '// Private function that supports the division of two numbers with
    '// a divisor that has only 1 digit.
    '//***********************************************************************

        private static void singleByteDivide(BigInteger bi1, BigInteger bi2,
                                             BigInteger outQuotient, BigInteger outRemainder)
        {
                uint[] result = new uint[maxLength]
                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(resultPos = 0)

                // copy dividend to reminder
                for(int i = 0 i < maxLength i++)
                        outRemainder.data[i] = bi1.data[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                            outRemainder.dataLength = bi1.dataLength

                while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
                        outRemainder.dataLength--

                ulong divisor = (ulong)bi2.data[0]
                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(pos = outRemainder.dataLength - 1)
                ulong dividend = (ulong)outRemainder.data[pos]

                //Console.WriteLine("divisor = " + divisor + " dividend = " + dividend)
                //Console.WriteLine("divisor = " + bi2 + "\ndividend = " + bi1)

                                                                                                                                                                                                                                                                                                                                                                                                                                                If (dividend >= divisor) Then
                {
                        ulong quotient = dividend / divisor
                        result[resultPos++] = (uint)quotient

                        outRemainder.data[pos] = (uint)(dividend % divisor)
                }
                pos--

                                                                                                                                                                                                                                                                                                                                                                                                                                                    While (pos >= 0)
                {
                        //Console.WriteLine(pos)

                        dividend = ((ulong)outRemainder.data[pos+1] << 32) + (ulong)outRemainder.data[pos]
                        ulong quotient = dividend / divisor
                        result[resultPos++] = (uint)quotient

                        outRemainder.data[pos+1] = 0
                        outRemainder.data[pos--] = (uint)(dividend % divisor)
                        //Console.WriteLine(">>>> " + bi1)
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                        outQuotient.dataLength = resultPos
                                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(j = 0)
                for(int i = outQuotient.dataLength - 1 i >= 0 i--, j++)
                        outQuotient.data[j] = result[i]
                for( j < maxLength j++)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                outQuotient.data([j] = 0)

                while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
                        outQuotient.dataLength--

                if(outQuotient.dataLength == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                        outQuotient.dataLength = 1

                while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
                        outRemainder.dataLength--
        }


    '//***********************************************************************
    '// Overloading of division operator
    '//***********************************************************************

        public static BigInteger operator /(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(quotient = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(remainder = New BigInteger())

                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Int(lastPos = maxLength - 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                            bool(divisorNeg = False, dividendNeg = False)

                if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                bi1 = -bi1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                dividendNeg = True
                }
                if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    bi2 = -bi2
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    divisorNeg = True
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    If (bi1 < bi2) Then
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return quotient
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                {
                        if(bi2.dataLength == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            singleByteDivide(bi1, bi2, quotient, remainder)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            multiByteDivide(bi1, bi2, quotient, remainder)

                        if(dividendNeg != divisorNeg)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return -quotient

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return quotient
                }
        }


    '//***********************************************************************
    '// Overloading of modulus operator
    '//***********************************************************************

        public static BigInteger operator %(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(quotient = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(remainder = New BigInteger(bi1))

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(lastPos = maxLength - 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                bool(dividendNeg = False)

                if((bi1.data[lastPos] & 0x80000000) != 0)     // bi1 negative
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    bi1 = -bi1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    dividendNeg = True
                }
                if((bi2.data[lastPos] & 0x80000000) != 0)     // bi2 negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        bi2 = -bi2

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        If (bi1 < bi2) Then
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return remainder
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Else
                {
                        if(bi2.dataLength == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                singleByteDivide(bi1, bi2, quotient, remainder)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                multiByteDivide(bi1, bi2, quotient, remainder)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (dividendNeg) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return -remainder

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return remainder
                }
        }


    '//***********************************************************************
    '// Overloading of bitwise AND operator
    '//***********************************************************************

        public static BigInteger operator &(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(result = New BigInteger())

                int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength

                for(int i = 0 i < len i++)
                {
                        uint sum = (uint)(bi1.data[i] & bi2.data[i])
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result.data([i] = sum)
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return result
        }


    '//***********************************************************************
    '// Overloading of bitwise OR operator
    '//***********************************************************************

        public static BigInteger operator |(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(result = New BigInteger())

                int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength

                for(int i = 0 i < len i++)
                {
                        uint sum = (uint)(bi1.data[i] | bi2.data[i])
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                result.data([i] = sum)
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return result
        }


    '//***********************************************************************
    '// Overloading of bitwise XOR operator
    '//***********************************************************************

        public static BigInteger operator ^(BigInteger bi1, BigInteger bi2)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(result = New BigInteger())

                int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength

                for(int i = 0 i < len i++)
                {
                        uint sum = (uint)(bi1.data[i] ^ bi2.data[i])
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result.data([i] = sum)
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result.dataLength = maxLength

                while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
                        result.dataLength--

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return result
        }


    '//***********************************************************************
    '// Returns max(this, bi)
    '//***********************************************************************

        public BigInteger max(BigInteger bi)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            If (this > bi) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return (New BigInteger(this))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return (New BigInteger(bi))
        }


    '//***********************************************************************
    '// Returns min(this, bi)
    '//***********************************************************************

        public BigInteger min(BigInteger bi)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (this < bi) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return (New BigInteger(this))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return (New BigInteger(bi))

        }


    '//***********************************************************************
    '// Returns the absolute value
    '//***********************************************************************

        public BigInteger abs()
        {
                if((this.data[maxLength - 1] & 0x80000000) != 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return (-this)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return (New BigInteger(this))
        }


    '//***********************************************************************
    '// Returns a string representing the BigInteger in base 10.
    '//***********************************************************************

        public override string ToString()
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return ToString(10)
        }


    '//***********************************************************************
    '// Returns a string representing the BigInteger in sign-and-magnitude
    '// format in the specified radix.
    '//
    '// Example
    '// -------
    '// If the value of BigInteger is -255 in base 10, then
    '// ToString(16) returns "-FF"
    '//
    '//***********************************************************************

        public string ToString(int radix)
        {
                if(radix < 2 || radix > 36)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Throw (New ArgumentException("Radix must be >= 2 and <= 36"))

                string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                string result = ""

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(a = this)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            bool(negative = False)
                if((a.data[maxLength-1] & 0x80000000) != 0)
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                negative = True
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Try
                        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    a = -a
                        }
                        catch(Exception) {}
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(quotient = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(remainder = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(biRadix = New BigInteger(radix))

                if(a.dataLength == 1 && a.data[0] == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result = "0"
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                {
                        while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))
                        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            singleByteDivide(a, biRadix, quotient, remainder)

                                if(remainder.data[0] < 10)
                                        result = remainder.data[0] + result
                                else
                                        result = charSet[(int)remainder.data[0] - 10] + result

                                a = quotient
                        }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (negative) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    result = "-" + result
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return result
        }


    '//***********************************************************************
    '// Returns a hex string showing the contains of the BigInteger
    '//
    '// Examples
    '// -------
    '// 1) If the value of BigInteger is 255 in base 10, then
    '//    ToHexString() returns "FF"
    '//
    '// 2) If the value of BigInteger is -255 in base 10, then
    '//    ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
    '//    which is the 2's complement representation of -255.
    '//
    '//***********************************************************************

        public string ToHexString()
        {
                string result = data[dataLength - 1].ToString("X")

                for(int i = dataLength - 2 i >= 0 i--)
                {
                        result += data[i].ToString("X8")
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return result
        }



    '//***********************************************************************
    '// Modulo Exponentiation
    '//***********************************************************************

        public BigInteger modPow(BigInteger exp, BigInteger n)
        {
			if((exp.data[maxLength-1] & 0x80000000) != 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Throw (New ArithmeticException("Positive exponents only."))

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(resultNum = 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(tempNum)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            bool(thisNegative = False)

	        if((this.data[maxLength-1] & 0x80000000) != 0)   // negative this
	        {
	            tempNum = -this % n
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                thisNegative = True
	        }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
	            tempNum = this % n  // ensures (tempNum * tempNum) < b^(2k)

	        if((n.data[maxLength-1] & 0x80000000) != 0)   // negative n
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    n = -n

            // calculate constant = b^(2k) / m
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(constant = New BigInteger())

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(i = n.dataLength << 1)
            constant.data[i] = 0x00000001
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    constant.dataLength = i + 1

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    constant = constant / n
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(totalBits = exp.bitCount())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(count = 0)

            // perform squaring and multiply exponentiation
            for(int pos = 0 pos < exp.dataLength pos++)
            {
                uint mask = 0x01
                //Console.WriteLine("pos = " + pos)

                for(int index = 0 index < 32 index++)
                {
                    if((exp.data[pos] & mask) != 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                resultNum = BarrettReduction(resultNum * tempNum, n, constant)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                mask <<= 1

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                tempNum = BarrettReduction(tempNum * tempNum, n, constant)

                    if(tempNum.dataLength == 1 && tempNum.data[0] == 1)
                    {
                            if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return -resultNum
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return resultNum
                    }
                    count++
                    if(count == totalBits)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            break()
                }
            }

            if(thisNegative && (exp.data[0] & 0x1) != 0)    //odd exp
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return -resultNum

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return resultNum
        }

    '//***********************************************************************
    '// Fast calculation of modular reduction using Barrett's reduction.
    '// Requires x < b^(2k), where b is the base.  In this case, base is
    '// 2^32 (uint).
    '//
    '// Reference [4]
    '//***********************************************************************

        private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
        {
                int k = n.dataLength,
                    kPlusOne = k+1,
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                kMinusOne = k - 1

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(q1 = New BigInteger())

                // q1 = x / b^(k-1)
                for(int i = kMinusOne, j = 0 i < x.dataLength i++, j++)
                        q1.data[j] = x.data[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    q1.dataLength = x.dataLength - kMinusOne
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    If (q1.dataLength <= 0) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        q1.dataLength = 1


                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(q2 = q1 * constant)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(q3 = New BigInteger())

                // q3 = q2 / b^(k+1)
                for(int i = kPlusOne, j = 0 i < q2.dataLength i++, j++)
                        q3.data[j] = q2.data[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            q3.dataLength = q2.dataLength - kPlusOne
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            If (q3.dataLength <= 0) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                q3.dataLength = 1


                // r1 = x mod b^(k+1)
                // i.e. keep the lowest (k+1) words
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(r1 = New BigInteger())
                int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength
                for(int i = 0 i < lengthToCopy i++)
                        r1.data[i] = x.data[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    r1.dataLength = lengthToCopy


                // r2 = (q3 * n) mod b^(k+1)
                // partial multiplication of q3 and n

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(r2 = New BigInteger())
                for(int i = 0 i < q3.dataLength i++)
                {
                        if(q3.data[i] == 0)     continue

                        ulong mcarry = 0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Int(t = i)
                        for(int j = 0 j < n.dataLength && t < kPlusOne j++, t++)
                        {
                                // t = i + j
                                ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
                                             (ulong)r2.data[t] + mcarry

                                r2.data[t] = (uint)(val & 0xFFFFFFFF)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                mcarry = (Val() >> 32)
                        }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (t < kPlusOne) Then
                                r2.data[t] = (uint)mcarry
                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    r2.dataLength = kPlusOne
                while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
                        r2.dataLength--

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        r1 -= r2
                if((r1.data[maxLength-1] & 0x80000000) != 0)        // negative
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(Val() = New BigInteger())
                        val.data[kPlusOne] = 0x00000001
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Val.dataLength = kPlusOne + 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            r1 += Val()
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            While (r1 >= n)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                r1 -= n

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return r1
        }


    '//***********************************************************************
    '// Returns gcd(this, bi)
    '//***********************************************************************

        public BigInteger gcd(BigInteger bi)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(x)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(y)

                if((data[maxLength-1] & 0x80000000) != 0)     // negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = -this
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = this

                if((bi.data[maxLength-1] & 0x80000000) != 0)     // negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        y = -bi
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        y = bi

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(g = y)

	        while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0))
	        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            g = x
		        x = y % x
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            y = g
        	}

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return g
        }

        public static BigInteger Random(int BitCount)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Random(rand = New Random(Environment.TickCount))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(b = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            b.genRandomBits(BitCount, rand)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return b
        }

    '//***********************************************************************
    '// Populates "this" with the specified amount of random bits
    '//***********************************************************************

        public void genRandomBits(int bits, Random rand)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Int(dwords = bits >> 5)
	        int remBits = bits & 0x1F

	        if(remBits != 0)
		        dwords++

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (dwords > maxLength) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Throw (New ArithmeticException("Number of required bits > maxLength."))

	        for(int i = 0 i < dwords i++)
		        data[i] = (uint)(rand.NextDouble() * 0x100000000)

	        for(int i = dwords i < maxLength i++)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            data([i] = 0)

	        if(remBits != 0)
	        {
		        uint mask = (uint)(0x01 << (remBits-1))
		        data[dwords-1] |= mask

		        mask = (uint)(0xFFFFFFFF >> (32 - remBits))
		        data[dwords-1] &= mask
	        }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
		        data[dwords-1] |= 0x80000000

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                dataLength = dwords

	        if(dataLength == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    dataLength = 1
        }


    '//***********************************************************************
    '// Returns the position of the most significant bit in the BigInteger.
    '//
    '// Eg.  The result is 0, if the value of BigInteger is 0...0000 0000
    '//      The result is 1, if the value of BigInteger is 0...0000 0001
    '//      The result is 2, if the value of BigInteger is 0...0000 0010
    '//      The result is 2, if the value of BigInteger is 0...0000 0011
    '//
    '//***********************************************************************

        public int bitCount()
        {
                while(dataLength > 1 && data[dataLength-1] == 0)
                        dataLength--

               uint value = data[dataLength - 1]
               uint mask = 0x80000000
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(bits = 32)

               while(bits > 0 && (value & mask) == 0)
               {
                        bits--
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            mask >>= 1
               }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            bits += ((dataLength - 1) << 5)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return bits
        }


    '//***********************************************************************
    '// Probabilistic prime test based on Fermat's little theorem
    '//
    '// for any a < p (p does not divide a) if
    '//      a^(p-1) mod p != 1 then p is not prime.
    '//
    '// Otherwise, p is probably prime (pseudoprime to the chosen base).
    '//
    '// Returns
    '// -------
    '// True if "this" is a pseudoprime to randomly chosen
    '// bases.  The number of chosen bases is given by the "confidence"
    '// parameter.
    '//
    '// False if "this" is definitely NOT prime.
    '//
    '// Note - this method is fast but fails for Carmichael numbers except
    '// when the randomly chosen base is a factor of the number.
    '//
    '//***********************************************************************

        public bool FermatLittleTest(int confidence)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(thisVal)
                if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                thisVal = -this
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                thisVal = this

                if(thisVal.dataLength == 1)
                {
                        // test small numbers
                        if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return False
                        else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return True
                }

                if((thisVal.data[0] & 0x1) == 0)     // even numbers
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return False

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Int(bits = thisVal.bitCount())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(a = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(p_sub1 = thisVal - (New BigInteger(1)))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Random(rand = New Random())

	        for(int round = 0 round < confidence round++)
	        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                bool(done = False)

		        while(!done)		// generate a < n
		        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(testBits = 0)

			        // make sure "a" has at least 2 bits
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    While (testBits < 2)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        testBits = (Int())(rand.NextDouble() * bits)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        a.genRandomBits(testBits, rand)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(byteLen = a.dataLength)

                                // make sure "a" is not 0
			        if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            done = True
		        }

                        // check whether a factor exists (fix for version 1.03)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(gcdTest = a.gcd(thisVal))
                        if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return False

		        // calculate a^(p-1) mod p
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(expResult = a.modPow(p_sub1, thisVal))

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(resultLen = expResult.dataLength)

                        // is NOT prime is a^(p-1) mod p != 1

		        if(resultLen > 1 || (resultLen == 1 && expResult.data[0] != 1))
		        {
		                //Console.WriteLine("a = " + a.ToString())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return False
                        }
	        }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return True
        }


    '//***********************************************************************
    '// Probabilistic prime test based on Rabin-Miller's
    '//
    '// for any p > 0 with p - 1 = 2^s * t
    '//
    '// p is probably prime (strong pseudoprime) if for any a < p,
    '// 1) a^t mod p = 1 or
    '// 2) a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
    '//
    '// Otherwise, p is composite.
    '//
    '// Returns
    '// -------
    '// True if "this" is a strong pseudoprime to randomly chosen
    '// bases.  The number of chosen bases is given by the "confidence"
    '// parameter.
    '//
    '// False if "this" is definitely NOT prime.
    '//
    '//***********************************************************************

        public bool RabinMillerTest(int confidence)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(thisVal)
                if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        thisVal = -this
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        thisVal = this

                if(thisVal.dataLength == 1)
                {
                        // test small numbers
                        if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return False
                        else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return True
                }

                if((thisVal.data[0] & 0x1) == 0)     // even numbers
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return False


                // calculate values of s and t
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(p_sub1 = thisVal - (New BigInteger(1)))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(s = 0)

                for(int index = 0 index < p_sub1.dataLength index++)
                {
                        uint mask = 0x01

                        for(int i = 0 i < 32 i++)
                        {
                                if((p_sub1.data[index] & mask) != 0)
                                {
                                        index = p_sub1.dataLength      // to break the outer loop
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                break()
                                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                mask <<= 1
                                s++
                        }
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(t = p_sub1 >> s)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(bits = thisVal.bitCount())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(a = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Random(rand = New Random())

	        for(int round = 0 round < confidence round++)
	        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    bool(done = False)

		        while(!done)		// generate a < n
		        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(testBits = 0)

			        // make sure "a" has at least 2 bits
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        While (testBits < 2)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            testBits = (Int())(rand.NextDouble() * bits)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            a.genRandomBits(testBits, rand)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Int(byteLen = a.dataLength)

                                // make sure "a" is not 0
			        if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                done = True
		        }

                        // check whether a factor exists (fix for version 1.03)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(gcdTest = a.gcd(thisVal))
                        if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return False

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(b = a.modPow(t, thisVal))

                        /*
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Console.WriteLine("a = " + a.ToString(10))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Console.WriteLine("b = " + b.ToString(10))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Console.WriteLine("t = " + t.ToString(10))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Console.WriteLine("s = " + s)
                        */

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    bool(result = False)

                        if(b.dataLength == 1 && b.data[0] == 1)         // a^t mod p = 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result = True

                        for(int j = 0 result == false && j < s j++)
                        {
                                if(b == p_sub1)         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
                                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                result = True
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                break()
                                }

                                b = (b * b) % thisVal
                        }

                        if(result == false)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return False
                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return True
        }

    '//***********************************************************************
    '// Determines whether a number is probably prime, using the Rabin-Miller's
    '// test.  Before applying the test, the number is tested for divisibility
    '// by primes < 2000
    '//
    '// Returns true if number is probably prime.
    '//***********************************************************************

        public bool isProbablePrime(int confidence)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(thisVal)
                if((this.data[maxLength-1] & 0x80000000) != 0)        // negative
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        thisVal = -this
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        thisVal = this


                // test for divisibility by primes < 2000
                for(int p = 0 p < primesBelow2000.Length p++)
                {
                        BigInteger divisor = primesBelow2000[p]

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            If (divisor >= thisVal) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                break()

                        BigInteger resultNum = thisVal % divisor
                        if(resultNum.IntValue() == 0)
                        {
                                /*
				Console.WriteLine("Not prime!  Divisible by {0}\n",
                                                  primesBelow2000[p])
                                */
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return False
                        }
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    If (thisVal.RabinMillerTest(confidence)) Then
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return True
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                {
                        //Console.WriteLine("Not prime!  Failed primality test\n")
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return False
                }
        }

    '//***********************************************************************
    '// Returns the lowest 4 bytes of the BigInteger as an int.
    '//***********************************************************************

        public int IntValue()
        {
                return (int)data[0]
        }


    '//***********************************************************************
    '// Returns the lowest 8 bytes of the BigInteger as a long.
    '//***********************************************************************

        public long LongValue()
        {
                long val = 0

                val = (long)data[0]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Try
                {       // exception if maxLength = 1
                        val |= (long)data[1] << 32
                }
                catch(Exception)
                {
                        if((data[0] & 0x80000000) != 0) // negative
                                val = (int)data[0]
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return Val()
        }


    '//***********************************************************************
    '// Computes the Jacobi Symbol for a and b.
    '// Algorithm adapted from [3] and [4] with some optimizations
    '//***********************************************************************

        public static int Jacobi(BigInteger a, BigInteger b)
        {
                // Jacobi defined only for odd integers
                if((b.data[0] & 0x1) == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Throw (New ArgumentException("Jacobi defined only for odd integers."))

                if(a >= b)      a %= b
                if(a.dataLength == 1 && a.data[0] == 0)      return 0  // a == 0
                if(a.dataLength == 1 && a.data[0] == 1)      return 1  // a == 1

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                If (a < 0) Then
                {
                        if( (((b-1).data[0]) & 0x2) == 0)       //if( (((b-1) >> 1).data[0] & 0x1) == 0)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return Jacobi(-a, b)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return -Jacobi(-a, b)
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Int(e = 0)
                for(int index = 0 index < a.dataLength index++)
                {
                        uint mask = 0x01

                        for(int i = 0 i < 32 i++)
                        {
                                if((a.data[index] & mask) != 0)
                                {
                                        index = a.dataLength      // to break the outer loop
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    break()
                                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    mask <<= 1
                                e++
                        }
                }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(a1 = a >> e)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(s = 1)
                if((e & 0x1) != 0 && ((b.data[0] & 0x7) == 3 || (b.data[0] & 0x7) == 5))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        s = -1

                if((b.data[0] & 0x3) == 3 && (a1.data[0] & 0x3) == 3)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            s = -s

                if(a1.dataLength == 1 && a1.data[0] == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return s
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Else
                        return (s * Jacobi(b % a1, a1))
        }



    '//***********************************************************************
    '// Generates a positive BigInteger that is probably prime.
    '//***********************************************************************

        public static BigInteger genPseudoPrime(int bits, int confidence, Random rand)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(result = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                bool(done = False)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                While (!done)
	        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    result.genRandomBits(bits, rand)
		        result.data[0] |= 0x01		// make it odd

		        // prime test
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    done = result.isProbablePrime(confidence)
	        }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Return result
        }


    '//***********************************************************************
    '// Generates a random number with the specified number of bits such
    '// that gcd(number, this) = 1
    '//***********************************************************************

        public BigInteger genCoPrime(int bits, Random rand)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    bool(done = False)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    BigInteger(result = New BigInteger())

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    While (!done)
	        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        result.genRandomBits(bits, rand)
	                //Console.WriteLine(result.ToString(16))

		        // gcd test
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(g = result.gcd(this))
			if(g.dataLength == 1 && g.data[0] == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            done = True
	        }

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Return result
        }


    '//***********************************************************************
    '// Returns the modulo inverse of this.  Throws ArithmeticException if
    '// the inverse does not exist.  (i.e. gcd(this, modulus) != 1)
    '//***********************************************************************

        public BigInteger modInverse(BigInteger modulus)
        {
                BigInteger[] p = { 0, 1 }
                BigInteger[] q = new BigInteger[2]    // quotients
                BigInteger[] r = { 0, 0 }             // remainders

                int step = 0

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(a = modulus)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            BigInteger(b = this)

                while(b.dataLength > 1 || (b.dataLength == 1 && b.data[0] != 0))
                {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(quotient = New BigInteger())
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                BigInteger(remainder = New BigInteger())

                        if(step > 1)
                        {
                                BigInteger pval = (p[0] - (p[1] * q[0])) % modulus
                                p[0] = p[1]
                                p[1] = pval
                        }

                        if(b.dataLength == 1)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        singleByteDivide(a, b, quotient, remainder)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        multiByteDivide(a, b, quotient, remainder)

                        /*
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Console.WriteLine(quotient.dataLength)
                        Console.WriteLine("{0} = {1}({2}) + {3}  p = {4}", a.ToString(10),
                                          b.ToString(10), quotient.ToString(10), remainder.ToString(10),
                                          p[1].ToString(10))
                        */

                        q[0] = q[1]
                        r[0] = r[1]
                        q[1] = quotient r[1] = remainder

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        a = b
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        b = remainder

                        step++
                }

                if(r[0].dataLength > 1 || (r[0].dataLength == 1 && r[0].data[0] != 1))
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            Throw (New ArithmeticException("No inverse!"))

                BigInteger result = ((p[0] - (p[1] * q[0])) % modulus)

                if((result.data[maxLength - 1] & 0x80000000) != 0)
                        result += modulus  // get the least positive modulus

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Return result
        }


    '//***********************************************************************
    '// Returns the value of the BigInteger as a byte array.  The lowest
    '// index contains the MSB.
    '//***********************************************************************

        public byte[] getBytes()
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(numBits = bitCount())

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                Int(numBytes = numBits >> 3)
                if((numBits & 0x7) != 0)
                        numBytes++

                byte[] result = new byte[numBytes]

                //Console.WriteLine(result.Length)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Int(pos = 0)
                uint tempVal, val = data[dataLength - 1]

                if((tempVal = (val >> 24 & 0xFF)) != 0)
                        result[pos++] = (byte)tempVal
                if((tempVal = (val >> 16 & 0xFF)) != 0)
                        result[pos++] = (byte)tempVal
                if((tempVal = (val >> 8 & 0xFF)) != 0)
                        result[pos++] = (byte)tempVal
                if((tempVal = (val & 0xFF)) != 0)
                        result[pos++] = (byte)tempVal

                for(int i = dataLength - 2 i >= 0 i--, pos += 4)
                {
                        val = data[i]
                        result[pos+3] = (byte)(val & 0xFF)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Val >>= 8
                        result[pos+2] = (byte)(val & 0xFF)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Val >>= 8
                        result[pos+1] = (byte)(val & 0xFF)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Val >>= 8
                        result[pos] = (byte)(val & 0xFF)
                }
                Array.Reverse(result) // Added by Foole

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return result
        }


    '//***********************************************************************
    '// Sets the value of the specified bit to 1
    '// The Least Significant Bit position is 0.
    '//***********************************************************************

        public void setBit(uint bitNum)
        {
                uint bytePos = bitNum >> 5             // divide by 32
                byte bitPos = (byte)(bitNum & 0x1F)    // get the lowest 5 bits

                uint mask = (uint)1 << bitPos
                this.data[bytePos] |= mask

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        If (bytePos >= this.dataLength) Then
                        this.dataLength = (int)bytePos + 1
        }


    '//***********************************************************************
    '// Sets the value of the specified bit to 0
    '// The Least Significant Bit position is 0.
    '//***********************************************************************

        public void unsetBit(uint bitNum)
        {
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            uint(bytePos = bitNum >> 5)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            If (bytePos < this.dataLength) Then
                {
                        byte bitPos = (byte)(bitNum & 0x1F)

                        uint mask = (uint)1 << bitPos
                        uint mask2 = 0xFFFFFFFF ^ mask

                        this.data[bytePos] &= mask2

                        if(this.dataLength > 1 && this.data[this.dataLength - 1] == 0)
                                this.dataLength--
                }
        }


    '//***********************************************************************
    '// Returns a value that is equivalent to the integer square root
    '// of the BigInteger.
    '//
    '// The integer square root of "this" is defined as the largest integer n
    '// such that (n * n) <= this
    '//
    '//***********************************************************************

		public BigInteger sqrt()
		{
            uint numBits = (uint)this.bitCount()

                if((numBits & 0x1) != 0)        // odd number of bits
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        numBits = (numBits >> 1) + 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Else
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        numBits = (numBits >> 1)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        uint(bytePos = numBits >> 5)
                byte bitPos = (byte)(numBits & 0x1F)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        uint(mask)

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        BigInteger(result = New BigInteger())
                if(bitPos == 0)
                        mask = 0x80000000
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Else
                {
                        mask = (uint)1 << bitPos
                        bytePos++
                }
                result.dataLength = (int)bytePos

                for(int i = (int)bytePos - 1 i >= 0 i--)
                {
                        while(mask != 0)
                        {
                                // guess
                                result.data[i] ^= mask

                                // undo the guess if its square is larger than this
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    If ((result * result) > this) Then
                                        result.data[i] ^= mask

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        mask >>= 1
                        }
                        mask = 0x80000000
                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        Return result
End Class

